package com.company.LinkList;

import org.omg.CORBA.PUBLIC_MEMBER;

import java.sql.Statement;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}18:48
 */
public class SingleLinkedList {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode headHero = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙");

        SingleLinkedListDemo singleLinkedList = new SingleLinkedListDemo();
        singleLinkedList.sortAdd(headHero);
        singleLinkedList.sortAdd(hero3);
        singleLinkedList.sortAdd(hero4);
        singleLinkedList.sortAdd(hero2);
        singleLinkedList.list();
        SingleLinkedListDemo.reversePrint(headHero);

    }


    static class HeroNode{
        public int no;
        public String name;
        public String nickname;
        public HeroNode next;

        public HeroNode(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    //定义SingleLinkedList 管理名单
    static class SingleLinkedListDemo{
        private HeroNode head = new HeroNode(0,"","");

        public void add(HeroNode heroNode){
            HeroNode temp = head;//辅助变量遍历，帮助遍历整个链表
            while (true){
                if (temp.next==null){
                    break;
                }
                temp = temp.next;
            }
            temp.next = heroNode;
        }

        public void sortAdd(HeroNode heroNode){
            HeroNode temp = head;//辅助变量遍历，帮助遍历整个链表
            while (true) {
                if (temp.next == null||temp == null) {
                    break;
                } else {
                    if (temp.next.no>heroNode.no){
                        break;
                    }
                }
                temp = temp.next;
            }
            heroNode.next = temp.next;
            temp.next = heroNode;

        }
        public void list(){
            if (head.next == null){
                System.out.println("链表为空");
                return;
            }

            HeroNode temp = head.next;
            while (true){
                if (temp == null){
                    System.out.println("链表到底");
                    break;
                }
                System.out.println(temp);
                temp = temp.next;
            }
        }

        //单链表递归排序
       public HeroNode sort(HeroNode pre,HeroNode cur){
            HeroNode pre1 = pre;
            HeroNode cur1 = cur;
            if (pre1 == null){
                return pre1;
            }
            if (cur1 == null){
                return cur1;
            }
            HeroNode node = null;
            if (pre1.no<cur1.no){
                node = pre1;
                node.next = sort(pre1.next,cur1);
            }
            if (pre1.no>cur1.no){
                node = cur1;
                node.next = sort(pre1,cur1.next);
            }
            return node;
       }

        /**
         * 反转链表
         * @param head
         */
        public static void reversetList(HeroNode head){
            if (head.next == null || head.next.next == null){//说明无需进行反转的条件（链表为空，只有一个节点// ）
                return;
            }

            //定义一个辅助指针（变量），帮助我们遍历原来的链表
            HeroNode cur = head.next;
            HeroNode next = null;//指向当前节点【cur】的下一个节点
            HeroNode reverseHead = new HeroNode(0,"","");
            //遍历原来的链表，并且从头到尾遍历原来的链表每次遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
            while (cur!=null){
                next = cur.next;//暂时保存当前节点的下一个节点，后面需要使用
                cur.next = reverseHead.next;
                reverseHead.next = cur;
                cur = next;
            }
            head.next = reverseHead.next;
        }

       //用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的结果
        public static void reversePrint(HeroNode head){
            if (head.next == null){
                return;
            }
            //创建一个栈，将各个节点压入栈
            Stack<HeroNode> stack = new Stack<HeroNode>();
            HeroNode cur = head.next;
            while (cur != null){
                stack.push(cur);
                cur = cur.next;//cur后移
            }
            while (stack.size()>0){
                System.out.println(stack.pop());
            }
        }

    }

}
